iT邦幫忙

2024 iThome 鐵人賽

DAY 22
3

沒想到能撐到現在,今天順便將明後天要介紹的Opening Book跟Endgame Database的大綱先擬好了,事到如今硬著頭皮也得完賽吧。
hackMD原稿

在Day4的時候有提到,對局樹會有很多重複的盤面出現,造成效能的浪費,未來會介紹到Transposition Table就能夠來處理這個問題。
奇異博士看到了上百萬個我棄賽的未來,沒看到的就是今天,我自己都沒想到。

Transposition Table

以空間換取時間

Transposition Table(同形表) 是用來儲存歷史盤面跟相關資訊的,避免在搜尋過程中重複計算已經評估過的棋局狀態。通過儲存已經搜索過的盤面及其相關資訊,當搜索中遇到相同的盤面時,直接從使用之前的結果,從而節省計算資源和時間。

重複盤面

再看一次上下兩條分支,雖然過程不同,但結果相同的情況。

再來就是這種旋轉跟鏡像對稱的盤面,其實都可以視為同一種。

在搜索的過程中,如果先把分支的結果給存下來,只要遇到重複的盤面就直接使用之前搜索過的結果,這樣就可以省去不必要的重複計算。
如下圖,本來 X 下在中間後,O 有8種下法,但實際上我們只需要搜索其中的2種,剩下的盤面都可以直接查詢歷史盤面,不用再重新搜索了。

初始盤面也是只需要搜索其中的3種,比前面介紹的所有剪枝都還要強大。

循環走步

Transposition Table也可以用來處理循環走步的問題。

  • 圍棋
    黑棋可以在A點將白棋給吃掉。
    image
    但就在黑棋提過去之後 A 點的棋子也只剩下一氣,白棋如果下在 B 點也可以把黑棋吃掉。
    image
    這樣雙方只要開始提來提去那這盤棋就沒完沒了了,所以圍棋有個規則是,當對方提過來時,我方必須隔一手之後才能提回去,這就是打劫
    這邊就可以檢查歷史盤面,來檢查是否有違規情況,比如上圖中黑棋下在 A 點將白棋吃掉後,白棋不能夠馬上於 B 點吃回去,必須先在其他地方落子,下一個回合後才能夠吃回來,如果白棋馬上吃回去,那就會跟歷史盤面有重複,所以只要有重複盤面就可以判定是違規。
    (三劫、四劫、長生劫等複雜循環行為這裡暫時不去探討)

  • 象棋
    長將、長捉、長殺(棋例)

  • 西洋棋
    三次重複

其他還有像是跳棋、Surakarta,都是很容易發生循環走步的遊戲,設計一個好的Transposition Table就會變得非常重要。

Zobrist Hashing

一開始在看井字遊戲大家可能不會有感覺,但是看一下象棋、西洋棋或是圍棋,要如何存下過往盤面資訊?
如果是用Array來表示棋盤資料結構的話,然後將每個盤面的Array都儲存下來,就算不考慮比對Array的效能。
圍棋隨便都能達到上百手,你在每個盤面展開的時候都得去比對前面一百個盤面,這樣線性搜索效能肯定是非常差的,這時候我們就會用到Hash。

image

圖片擷取自how programmers overprepare for job interviews,這影片太好笑了一定要點進去看!

而Zobrist Hashing應該是目前最常見的建同形表的方式,Day16也有提到過一個Zobrist's Model,沒錯!這兩個Zobrist是同一位,就是Albert Zobrist

Zobrist Hashing 通過給每個棋子在每個位置上分配一個隨機的二進制數字(hash值),來表示盤面。當棋子移動時,可以使用位元運算快速更新整個棋盤的hash值,而不必重新計算整個盤面的hash值。
正常情況你得給新的盤面一個新的hash值,但Zobrist Hashing只針對移動的棋子做XOR,效率會高非常多。

步驟

以西洋棋為例,步驟如下:

  1. 初始化隨機數表
    為每個棋子的每個可能位置分配一個隨機的 64 位整數,西洋棋的隨機數表的大小約為:
    12 種棋種 × 64 個棋盤位置 = 768 個隨機數
  2. 盤面hash值的生成
    遍歷棋盤上的每個位置,根據當前該位置的棋子類型和位置,查詢對應的隨機數,並通過XOR運算將這些隨機數組合成一個唯一的hash值,來表示當前盤面。
  3. 更新hash值
    每當一個棋子移動時:
    將棋子移動前的位置與其對應的隨機數進行XOR,表示移開該棋子。
    將棋子移動後的新位置與對應的隨機數進行XOR,表示棋子已到新位置。

步驟1可以一開始就產生好,不用每次遊戲都產生一個新的隨機數表,比如在Deep Learning and the Game of Go這個開源程式中,他已經先建立好一個HASH_CODE,實際的操作範例可以看goboard_fast.py

XOR(exclusive or)的特性

詳細XOR的特性與證明請至邏輯互斥或查看。

  • 交換律:
  • 結合律:

因為這兩個特性,XOR不會被順序影響,無論棋子移動順序如何,結果hash值一致。

  • 運算元的單位值:


    這樣放置棋子與移除棋子相當方便,如果是移動的話就等同於先移除再放置,操作順序一樣不影響。

優點

  • 快速局面更新:只需針對少數位置進行XOR操作,更新速度非常快。
  • 減少重複搜索:能識別不同手順導致的相同盤面,避免重複計算。
  • 空間效率高:hash值用固定大小(64 位整數)表示,不必存整個棋盤狀態。

缺點

  • 碰撞問題:不同盤面會生成相同hash值,但在實際應用中,這種機率非常低,可以忽略。
    使用64位元的hash值若搜尋 (約42億)個節點數,碰撞機率為 ,比中樂透機率還低。
    (這個數據引用自電腦對局導論,書中有詳細推導過程,歡迎大家去買書,這裡就不展開了。)

結論

Transposition Table對於對局樹的搜索來說相當重要,可能你費盡心思做了一大堆剪枝,都不如實作一個Transposition Table,對效能的影響非常的大。使用Zobrist Hashing可以用相對小的空間儲存各種棋盤狀態,並且能利用位元運算XOR快速更新,現在就為你的程式實作一個吧!
本來還想寫一點當Transposition Table滿了之後的一些置換策略,但想到現在的記憶體隨便都16G、32G,還非常便宜,就不用考慮Transposition Table的大小了吧。

Reference


上一篇
Day21 Board Representation
下一篇
Day23 Opening Book
系列文
猴子也能懂的電腦對局 : 30天打造自己的對局AI30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言